package com.foxzzz.dynamic.programming;

import com.foxzzz.base.GenUtil;

public class Solution63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid.length==0||obstacleGrid[0].length==0||obstacleGrid[0][0]==1)
            return 0;
        int[][] dp=new int[obstacleGrid.length][obstacleGrid[0].length];
        dp[0][0] = 1;
        for (int i = 1; i < obstacleGrid.length; i++) {
            dp[i][0]=obstacleGrid[i][0]==1?0:dp[i-1][0];
        }
        for (int j = 1; j < obstacleGrid[0].length; j++){
            dp[0][j]=obstacleGrid[0][j]==1?0:dp[0][j-1];
        }
        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                dp[i][j]=obstacleGrid[i][j]==1?0:dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }

    public static void main(String[] args) {

        System.out.println(new Solution63().uniquePathsWithObstacles(GenUtil.genIntTestCast("[[0,0,0],[0,1,0],[0,0,0]]",3,3)));
    }
}
